Each device on the Internet is assigned an Internet Protocol (IP) address which allows that device to be located for purposes of communication with other devices. There are two versions of IP that are currently in use—IP version 4 (IPv4) and IP version 6 (IPv6)—which each have their own form of IP address. In particular, an IP version 4 address comprises 32 bits and is divided into 4 octets such that it takes the form A.B.C.D where each of A, B, C, and D is a decimal number between 0 and 255. An IP version 6 address comprises 128 bits and is divided into 8 groups of four hexadecimal numbers such that it takes the form K:L:M:N:O:P:Q:R where each of K, L, M, N, O, P, Q and R is a hexadecimal number between 0000 and FFFF.
Since there are more than 4.2 billion possible IPv4 addresses, if there were no organization of the IP address it would be very difficult to locate a particular IP address in the Internet. Devices would have to keep track of all 4.2 billion addresses and how to get to each address. Accordingly, to make it easier to locate an IP address on the Internet, contiguous IP addresses (in either form) are grouped together into what is referred to as a sub-network or subnet. IP addresses that belong to the same subnet share a certain number of most significant bits (i.e. the first part of their IP addresses are the same) and the remaining least significant bits are used to uniquely identify the device associated with the IP address. Accordingly, an IP address can be divided into a routing prefix (the shared bits) and a host identifier.
A prefix is generally represented by the first address of the subnet, followed by a slash “/” then a number defining how many bits are in the prefix. This number is referred to as the subnet mask. For example 192.168.1.0/24 is an IPv4 prefix that starts at address 192.168.1.0 and covers the first 24 bits of the address, leaving 8 bits to be used for device addresses. Therefore the last address of the subnet is 192.168.1.255. The subnet mask can also be expressed as a dot-decimal notation in the same way as an IP address. For example, a 24 bit subnet mask can be represented in the form 255.255.255.0.
Organizations can be assigned one or more prefixes. All of the prefixes under the control of a single organization form what is referred to an autonomous system (AS). Each AS is assigned a globally unique number referred to as an autonomous system number (ASN) which uniquely identifies the AS. The autonomous systems are connected together to allow communication between autonomous systems.
The autonomous Systems use an Exterior Gateway Protocol (EGP) to exchange routing information and to route traffic between autonomous systems. Border Gateway Protocol (BGP) version four is currently the de-facto standard EGP for inter-AS routing. Each AS uses BGP to notify any other AS that it is connected to of the prefixes that it is responsible for (e.g. has been assigned) and any other prefixes that is knows about. Each AS stores the information about all the prefixes it knows about (e.g. those that are local to it and those that it has learned about from other autonomous systems) and what the possible routes are to each prefix. Each AS then uses one or more metrics to select the best route to each prefix from the list of possible routes. In this way each AS only needs to keep track of each prefix instead of each IP address. However, an EGP (e.g. BGP) typically only indicates the next EGP router in the path and thus another routing protocol may be required to route the traffic between EGP routers.
Autonomous systems can be categorized into one of three types: stub, multihomed or transit. A stub AS is an AS that is connected to only one other AS. A multihomed AS is connected to at least two ASs for backup purposes so that Internet connectivity can be maintained in the event of a failure of connection to one of the autonomous systems. This type of AS does not, however, allow traffic from one AS to pass through on its way to another AS. In contrast, a transit AS is an AS that is connected to multiple autonomous systems and provides connections through itself to other autonomous systems. For example, AS1 may use AS2, a transit AS, to connect to AS3. A transit AS uses BGP to route traffic between autonomous systems (e.g. traffic from AS1 to AS3). A transit AS will typically also be able to be the originator and/or termination point of traffic.
A transit AS comprises a complex network of routers using BGP (which are referred to herein as BGP routers) to route traffic from one AS to another (including to/from the transit AS itself). The BGP routers are typically configured to send traffic via the most efficient route through the transit AS network so that the traffic spends as little time as possible in the transit AS network. However, transit AS networks are not generally well designed to deal with failures in the network (e.g. failure of a link or router), particularly multiple failures. This is partly because transit AS networks are so complicated that is not immediately evident how traffic will be routed upon a failure. As a result, a failure or multiple failures can have a catastrophic effect on the network. For example, traffic normally sent over a failed link may be re-routed over an already busy link which may cause the busy link to become overloaded bringing performance over that link down to an unacceptable level.
Accordingly, there is a desire to be able to determine the effect of failures (e.g. node link, or peering failures) on a transit AS. In particular, there is a desire to be able to determine how traffic will be re-routed through a transit AS network upon a failure or multiple failures.
The embodiments described below are not limited to implementations which solve any or all of the disadvantages of known network analysis systems.